package com.mlh.binarysearch;

/**
 * @author 缪林辉
 * @date 2024/8/29 20:37
 * @DESCRIPTION
 */
//给你一个满足下述两条属性的 m x n 整数矩阵：
// 每行中的整数从左到右按非严格递增顺序排列。
// 每行的第一个整数大于前一行的最后一个整数。
// 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
public class 搜索二维矩阵 {
    public boolean method1(int[][] matrix, int target) {
        //先确定在哪一行
        int row=matrix.length-1,col=matrix[0].length-1;
        int resRow=0;
        while (resRow<row){
            if(matrix[resRow][0]<=target&&matrix[resRow][col]>=target){
                break;
            }
            resRow++;
        }
        //确定了之后在对改行进行二分查找
        if(resRow<=row){
            int left=0,right=col;
            while(left<=right){
                int mid=(left+right)/2;
                if(matrix[resRow][mid]==target){
                    return true;
                }else if(matrix[resRow][mid]>target){
                    right=mid-1;
                }else {
                    left=mid+1;
                }

            }
        }
        return false;
    }
   // 方法二：若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。
    // 代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。
   public boolean method2(int[][] matrix, int target) {
        int row=matrix.length,col=matrix[0].length;
        int left=0,right=row*col-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(matrix[mid/col][mid%col]==target){
                return true;
            }else if(matrix[mid/col][mid%col]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return false;
   }

    public boolean practice(int[][] matrix, int target) {
        int row=matrix.length,col=matrix[0].length,left=0,right=row*col-1;
        while(left<=right){
            int mid=(left+right)/2;
            int midRow=mid/col;
            int midCol=mid%col;
            if(matrix[midRow][midCol]>target){
                right=mid-1;
            }else if(matrix[midRow][midCol]<target){
                left=mid+1;
            }else {
                return true;
            }
        }
        return false;
    }
}
